package acwing._1_1AlgorithmBasic;

/**
 * @Project : ProgrammingExercises
 * @Package : ACWing.Learning.AlgorithmTemplate
 * @File : _2_4Trie.java
 * @Author : WangRuoyu
 * @Date 2023/3/12 10:23
 */

public class _2_4Trie {
    private int son[][] = new int[100010][26];
    private int cnt[] = new int[100010];
    private int idx = 1;
    private final int root = 0;

    public void insertString(String s) {
        int p = root;
        for (int i = 0; i < s.length(); ++i) {
            int u = s.charAt(i) - 'a';
            if (son[p][u] == 0) {
                son[p][u] = idx;
                idx++;
            }
            p = son[p][u];
        }
        cnt[p]++;
    }

    public int queryString(String s) {
        int p = root;
        for (int i = 0; i < s.length(); ++i) {
            int u = s.charAt(i) - 'a';
            if (son[p][u] == 0) {
                return 0;
            }
            p = son[p][u];
        }
        return cnt[p];
    }
}
